class Solution {
    public boolean canPartition(int[] nums) {
        int n = nums.length;
        if (n < 2) return false;
        int sum = 0, maxNum = 0;
        for (int num : nums) {
            sum += num;
            maxNum = Math.max(maxNum, num);
        }
        if (sum % 2 == 1){
            return false;
        }
        int target = (sum >> 1);
        if (maxNum > target){
            return false;
        }

        // 创建二维数组 dp\textit{dp}dp，包含 nnn 行 target+1\textit{target}+1target+1 列，其中 dp[i][j]\textit{dp}[i][j]dp[i][j] 表示从数组的 [0,i][0,i][0,i] 下标范围内选取若干个正整数（可以是 000 个），是否存在一种选取方案使得被选取的正整数的和等于 jjj。初始时，dp\textit{dp}dp 中的全部元素都是 false\text{false}false。
        /*
        boolean[][] dp = new boolean[n][target+1];
        for (int i = 0; i < n; i++){
            dp[i][0] = true;
        } 
        dp[0][nums[0]] = true;
        for (int i = 1; i < n; i++){
            int num = nums[i];
            for (int j = 1; j <= target; j++){
                if (j >= num){
                    dp[i][j] = dp[i-1][j] | dp[i-1][j-num];
                } else {
                    dp[i][j] = dp[i-1][j];
                }
            }
        }
        return dp[n-1][target];
        */
        boolean[] dp = new boolean[target+1];
        dp[0] = true;
        for (int i = 0; i < n; i++){
            int num = nums[i];
            for (int j = target; j >= num; j--){
                dp[j] |= dp[j-num];
            }
        }
        return dp[target];
    }
}